Statisticians, data analysts, etc. work with different representations of data sets in order to extract various features of the data not obvious from the raw data set alone. One such data representation that may be formed is a histogram. In a typical visually represented form, a histogram is a statistical graph, e.g., a bar graph, showing a frequency distribution, or some function thereof, in which the heights of vertical rectangles are proportionate to corresponding frequencies. In the context of image processing, histograms are often used to characterize image intensities, color, frequency content, and other characteristics of the image data or some derivative function of the image data. A suitable representation of a histogram for purposes of forming, storing and processing in digital computers is an array of counts, with each array element corresponding to a vertical rectangle in the graphical histogram, e.g., to occurrences of a particular intensity, color, frequency, etc. For example, an array of 256 elements [0 . . . 255] could hold the counts for each of the 256 possible gray scale pixel values in an 8-bit image. Many other statistics relating to the pixel values can be derived from or are calculated incident to such a histogram generation as well, including the number of pixels and the minimum, maximum, average and median pixel values. Additionally, function results or data sets derived from image data, such as the difference between two images, also may be statistically characterized by a histogram. Further, a histogram may be computed for any data set, not just for image data and derivatives of image data, such as a data set representing a certain population and corresponding ages, heights, weights, eye color and/or any characteristic that may describe the population in some way.
With increased sophistication and complexity of image processing in today's graphics applications and processes, a number of problems arise with histogram implementation. A main problem is that the size of the array needed to represent an exhaustive histogram increases exponentially with the precision of the values being characterized; for example, while a histogram for an 8-bit image requires a 256 (28) element array, the histogram for a 16-bit image requires 65,536 (216) values. Besides the hardware costs of maintaining these large arrays, proportionately more computation power is needed to process them; and if the histograms are computed by hardware components other than the host processor, the cost of copying histogram arrays into memory accessible by the host for further processing also increases proportionately.
With the advent of higher precision for pixel representation and programmable shading languages that enable complex computations to be performed on pixel data, it is becoming more and more desirable to compute histograms for intermediate processing results, which may or may not be pixel data, with much higher precision and speed. For example, commonly assigned copending U.S. patent application Ser. No. 09/801,079, filed Mar. 6, 2001, entitled “API Communications for Vertex and Pixel Shaders” (the '079 application) describes systems and methods employing such complex programmable shading language for communicating with specialized hardware implementations of vertex shaders and pixel shaders. Communications are provided for vertex shaders that may make use of a register index and that enable direct access to communications included within the graphics chip itself. Communications are also provided for specialized functionality implemented on-chip at a register level for increased processing speed and decreased memory transfer time between host and chip. Further, communications are provided for pixel shaders for specialized functionality, also implemented on-chip at a register level, including linear interpolation functionality and various modification functionality including negating, complementing, remapping, biasing, scaling and saturating.
Advantageously, with the system of the '079 application, the communications expose very useful on-chip graphical algorithmic elements to a developer while hiding the details of the operation of the vertex shader and pixel shader chips from the developer. Many of these functions implicate the very fast processing of data as it is passed through a graphics chip, bypassing the main memory stack and relatively slow processing of the host processor; however, the '079 application does not specifically describe the provision of a low cost, high speed histogram computation mechanism.
To further illustrate the current problems of histogram computation in connection with today's graphics applications, it may be instructive to understand the volumes of data associated with image processing applications. With many modem three dimensional (3-D) graphics systems, 3-D shapes are created by connecting a number of two-dimensional (2-D) polygons and curved surfaces are represented by connecting many small polygons. The view of a 3-D shape composed of polygon outlines is called a wire frame view. In sum, the computer creates 3-D objects by connecting a number of 2-D polygons. Before the 3-D object is ultimately rendered on a 2-D display screen, however, the data of a sophisticated graphics object undergoes many different mathematical transformations that implicate considerably specialized equations and processing unique to 3-D representation.
Early systems could only ascribe a single value to shading parameters and hence they remained constant and uniform across the entire surface of the object. Later systems allowed for the use of non-uniform parameters, transparency for instance, which might have different values over different parts of the object. Two prominent and distinct techniques have emerged to describe the values taken by these non-uniform parameters on the various parts of the object's surface: procedural shading and texture mapping. Texture mapping is pixel based and resolution dependent.
Procedural shading describes the appearance of a material at any point of a one dimensional (1-D), 2-D or 3-D space by defining a function, often called the procedural shader, in this space into shading parameter space. The object is “immersed” in the original 1-D, 2-D or 3-D space and the values of the shading parameters at a given point of the surface of the object are defined as a result of the procedural shading function at this point. For instance, procedural shaders that approximate appearance of wood, marble or other natural materials have been developed and can be found in the literature.
The rendering of graphics data in a computer system is thus a collection of resource intensive processes on volumes of 3-D data. The process of shading, i.e., the process of performing complex techniques upon set(s) of specialized graphics data structures, used to determine values for certain primitives, such as color, etc., associated with the graphics data structures, exemplifies such a computation intensive and complex process. For each developer to design these shading techniques for each program and/or for each developer to design each program for potentially varying third party graphics hardware would be a Herculean task, and would produce much inconsistency. The '079 application, described above, thus solves such a problem in connection with specialized procedural shading applications. However, there remains a need to remove the programming of complex histogram computational ability from the task list of the developer, and to move such functionality into the graphics pipeline itself.
While there are some prior art systems that provide limited statistical analysis on data, these systems implement pre-fixed functionality upon data for a predetermined reason, and consequently are hard-wired and immutable and thus do not offer the flexibility to analyze data from a variety of histogram perspectives. For example, translation boards exist that perform prefixed functionality on input data, which operate in the same way on an input data set, and which implement the same fixed function from an output perspective. Additionally, with those systems, the input data is limited to 8-bit gray scale pixel data.
A system is also known wherein one or more registers are implemented that keep track of passed-failed counts of z-buffer comparisons. However, with that system, not only is the implementation of a pre-fixed type, but also the resulting data set could not be accessed except through the use of a complex proprietary mechanism, further restricting the flexibility of the system.
Thus, there is a need for a way to incorporate histograms of variable precision into complex image processing pipelines such as those implemented by 3-D rasterization hardware. Further, since the internal precision of such hardware is typically 9 bits today and is anticipated to increase to 16 or more bits in the near future, and since such hardware may be separated from the host processor by a bus with limited data throughput, it would be desirable to provide a method for computing a smaller histogram that statistically characterizes input data while conserving the amount of data computed, transferred and processed. It would be further desirable to provide for such histogram functionality on a graphics chip, such that as data is streamed through the data rasterization pipeline, for display or storage, statistical histogram data may be extracted at the same time. It would be still further desirable to provide the ability to specify a mask for application to histogram data, either to the input data itself before histogram computation, or to the resulting histogram data in order to extract the most relevant data from the input data set.